package main

func DichSearch(s []int, target int) bool {
	l := len(s)
	if l == 0 || s[0] > target {
		return false
	}
	if s[l-1] < target {
		return false
	}
	head := 0
	tail := l - 1
	middle := (l - 1) / 2

	for {
		if s[middle] == target {
			return true
		}

		if middle == head {
			if s[tail] == target {
				return true
			}
			return false
		}

		if head == tail {
			return false
		}

		if s[middle] > target {
			tail = middle
			middle = (tail-head)/2 + head
			continue
		}
		if s[middle] < target {
			head = middle
			middle = (tail-head)/2 + head
			continue
		}
	}
}
func searchMatrix(matrix [][]int, target int) bool {
	m := len(matrix)
	n := len(matrix[0])
	if m == 0 || matrix[0][0] > target || matrix[m-1][n-1] < target {
		return false
	}

	var mid int = m - 1
	for i := 1; i < m; i++ {
		if matrix[i][0] > target {
			mid = i - 1
			break
		}
	}

	return DichSearch(matrix[mid], target)
}
